import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by L.jp
 * Description:请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。
 *
 * 二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#）
 *
 * 二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
 * User: 86189
 * Date: 2022-06-29
 * Time: 18:51
 */
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    
    public TreeNode(int val) {
        this.val = val;
        
    }
}
/**
 * @author 86189
 */
public class Solusion {
    //根据题目的提示，可以根据二叉树层次遍历来构造字符串，需要使用StringBuilder拼接字符串，
    // 层序遍历二叉树我们借助队列的结构
    String Serialize(TreeNode root) {
        if(root == null){
            return "#";
        }
        //由于下面一开始是先拼接数字字符，而不是数字，所以需要有一个前导的字符串作为拼接准备，可以是任意的只要不与题目的字符串相冲突即可
        //因为题目说了对序列化之后的字符串进行约束，所以格式可以是任意的
        StringBuilder sb = new StringBuilder("[");
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add( root );
        while ( !queue.isEmpty() ){
            TreeNode cur=queue.poll();
            if(cur != null){
                sb.append( cur.val ).append( "," );
                queue.add(cur.left);
                queue.add( cur.right );
            }else{
                //节点为空就拼接“#”
                sb.append( "#," );
            }
        }
        //没有节点了，就要把字符串的最后一个“，“删去
        sb.deleteCharAt( sb.length()-1 );
        sb.append( "]" );
        //不会消去"[]"，但是题目会处理好
        return sb.toString();
    }
    //根据层次遍历的字符串来完成二叉树的构建，借助队列完成二叉树的层次遍历构建二叉树
    TreeNode Deserialize(String str) {
        if("#".equals( str )){
            return null;
        }
        //把字符串换成字符串数组
        String[] tree=str.substring( 1,str.length() - 1 ).split( "," );
        TreeNode root=new TreeNode( Integer.parseInt(tree[0]));
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        //遍历字符串数组，已经遍历了根节点，直接从第二个节点开始
        int i=1;
        while ( !queue.isEmpty() ){
            //根据弹出的节点构造左右子树
            TreeNode cur=queue.poll();
            //如果字符串数组的元素不为空，说明不是空节点
            if(!"#".equals( tree[i] )){
                //拼接左子树
                cur.left=new TreeNode( Integer.parseInt( tree[i] ));
                //把左子树加入队列，后面还要构建
                queue.add(cur.left);
            }
            //不管是不是遇到了空节点都还要往后面构建
            i++;
            if(!"#".equals( tree[i] )){
                //拼接右子树
                cur.right=new TreeNode( Integer.parseInt(tree[i]) );
                //把右子树加入队列
                queue.add( cur.right );
            }
            //继续往后面构建
            i++;
        }
        return root;
    }
}
